import java.util.Stack;

public class ConvertBST {

    int temp = 0;
    public TreeNode convertBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        int temp = 0;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.right;
            }
            node = stack.pop();
            node.val += temp;
            temp = node.val;
            node = node.left;
        }
        return root;
    }

    public void process(TreeNode node) {
        if (node == null) return;
        process(node.right);
        node.val += temp;
        temp = node.val;
        process(node.left);
    }
}
